import java.util.*;

public class Test {
    //BM16 删除有序链表中重复的元素-II
    //哈希表
    //时间复杂度：O(N) 空间复杂度:O(N)
    public ListNode deleteDuplicates (ListNode head) {
        // write code here
        if(head == null) {
            return null;
        }
        ListNode cur = head;
        Map<Integer,Integer> map = new HashMap<>();
        //K-V 是 val值-出现的次数
        //把数据都放进哈希表中，并记录次数
        while(cur != null) {
            if(map.containsKey(cur.val)) {
                map.put(cur.val,(int)map.get(cur.val) + 1);
            }else {
                map.put(cur.val,1);
            }
            cur = cur.next;
        }
        ListNode ret = new ListNode(-1);
        ret.next = head;
        ListNode pre = ret;
        cur = ret.next;
        while(cur != null) {
            if(map.get(cur.val) != 1) {
                cur = cur.next;
                pre.next = cur;
            }else {
                pre = cur;
                cur = cur.next;
            }
        }
        return ret.next;
    }
    //双指针法
    //时间复杂度：O(N) 空间复杂度:O(1)
    public ListNode deleteDuplicates2 (ListNode head) {
        // write code here
        if(head == null) {
            return null;
        }
        ListNode ret = new ListNode(-1);
        ret.next = head;
        ListNode pre = ret;
        ListNode cur = ret.next;
        while(cur != null && cur.next != null) {
            //相邻的元素相等
            if(cur.val == cur.next.val) {
                //记录这个数据
                int temp = cur.val;
                while(cur != null && cur.val == temp) {
                    cur = cur.next;
                }
                pre.next = cur;
            }else {
                pre = cur;
                cur = cur.next;
            }
        }
        return ret.next;
    }

    //BM15 删除有序链表中重复的元素-I
    public ListNode deleteDuplicates1 (ListNode head) {
        // write code here
        if (head == null || head.next == null) {
            return head;
        }
        ListNode pre = head;
        ListNode cur = head.next;
        while(cur != null) {
            if(cur.val == pre.val) {
                pre.next = cur.next;
                cur = cur.next;
            }else {
                pre = cur;
                cur = cur.next;
            }
        }
        return head;
    }

    //BM14 链表的奇偶重排
    public ListNode oddEvenList (ListNode head) {
        // write code here
        //使用双指针
        //一个节点为奇数节点
        //一个节点为偶数节点
        //每次的奇数节点的下一个为偶数节点的下一个，之后把奇数节点移动到偶数的下一个位置
        //每次的偶数节点的下一个为奇数节点的下一个，之后把偶数节点移动到奇数的下一个位置
        if(head == null){
            return head;
        }
        ListNode odd = head;//奇数
        ListNode even = head.next;//偶数
        ListNode evenH = even;//记录偶数节点的头结点，为了在奇节点后面指向偶节点
        while(even != null && even.next != null) {
            //找奇数
            odd.next = even.next;
            odd = even.next;
            //找偶数
            even.next = odd.next;
            even = odd.next;
        }
        //连接奇偶节点
        odd.next = evenH;

        return head;
    }

    //BM13 判断一个链表是否为回文结构
    //转换成数组进行判断，但是不建议使用
    public boolean isPail (ListNode head) {
        // write code here
        //转化成数组进行判断
        ArrayList<Integer> list = new ArrayList<>();
        ListNode cur = head;
        while(cur != null) {
            list.add(cur.val);
            cur = cur.next;
        }
        int left = 0;
        int right = list.size() - 1;
        while(left <= right) {
            int v1 = list.get(left);
            int v2 = list.get(right);
            if(v1 != v2) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }

    //BM12 单链表的排序
    //使用数组进行排序
    public ListNode sortInList2 (ListNode head) {
        // write code here
        //转换成数组进行排序，再放到链表中
        ArrayList<Integer> list = new ArrayList<>();
        ListNode cur = head;
        //把节点的值放入到数组中
        while (cur != null) {
            list.add(cur.val);
            cur = cur.next;
        }
        //重新设置一下cur
        cur = head;
        //进行排序
        Collections.sort(list);
        //重新放入
        for (int i = 0; i < list.size(); i++) {
            cur.val = list.get(i);
            cur = cur.next;
        }
        return head;
    }
    //合并两个链表
    private ListNode merge (ListNode h1,ListNode h2) {
        if(h1 == null) {
            return h2;
        }
        if(h2 == null) {
            return h1;
        }
        ListNode head = new ListNode(-1);
        ListNode cur = head;
        while(h1 != null && h2 != null) {
            if(h1.val <= h2.val) {
                cur.next = h1;
                h1 = h1.next;
            }else {
                cur.next = h2;
                h2 = h2.next;
            }
            cur = cur.next;
        }
        //判断是否还有剩余的节点
        if(h1 != null) {
            cur.next = h1;
        }
        if(h2 != null) {
            cur.next = h2;
        }
        return head.next;
    }
    public ListNode sortInList (ListNode head) {
        // write code here
        //分治加双指针加递归
        if(head == null || head.next == null) {
            return head;
        }
        //我们设置一个left，mid，right
        ListNode left = head;//为了使找到中间结点之后使其断开和中间节点前面的节点，这样可以分为两个链表
        ListNode mid = head.next;//慢指针
        ListNode right = head.next.next;//快指针
        //之后我们left和mid一步步走，right呢两步步走
        //当right或者right.next为null的时候呢，我们的mid就是在中间位置
        while(right != null && right.next != null) {
            left = left.next;
            mid = mid.next;
            right = right.next.next;
        }
        //比如[1,3,2,4,5]
        //这时候left为3，mid为2，right为5
        //这个时候呢，我们的left在mid前一个节点，这时断开节点，使其分为两个链表
        left.next = null;
        //断开节点之后：[1,3] [2,4,5]
        return merge(sortInList(head),sortInList(mid));
    }

    //BM8 链表中倒数最后k个结点
    public ListNode FindKthToTail (ListNode pHead, int k) {
        // write code here
        //双指针，快的指针先走k步，之后它们在一起走
        //当fast这个指针，为空的时候，slow就是我们的要返回的第一个节点
        ListNode fast = pHead;
        ListNode slow = pHead;
        for(int i = 0;i < k ;i++) {
            if(fast != null) {
                fast = fast.next;
            }else {
                return null;
            }
        }

        while(fast != null) {
            slow = slow.next;
            fast = fast.next;
        }

        return slow;
    }

    //BM5 合并k个已排序的链表
    //双指针+分治 相当于是归并排序的思想
    //时间复杂度：O(NlogN) 空间复杂度：O(logN)
    public ListNode Merge (ListNode pHead1, ListNode pHead2) {
        // write code here
        //先判断，是否有空的
        if (pHead1 == null) {
            return pHead2;
        }
        if (pHead2 == null) {
            return pHead1;
        }
        ListNode head = new ListNode(-1);
        ListNode cur = head;

        while (pHead1 != null && pHead2 != null) {
            if (pHead1.val <= pHead2.val) {
                cur.next = pHead1;
                pHead1 = pHead1.next;
            } else {
                cur.next = pHead2;
                pHead2 = pHead2.next;
            }
            cur = cur.next;
        }

        if (pHead1 == null) {
            cur.next = pHead2;
        } else {
            cur.next = pHead1;
        }
        return head.next;
    }
    private ListNode divideMerge(ArrayList<ListNode> lists, int left, int right) {
        if (left > right) {
            return null;
        }
        if (left == right) {
            return lists.get(left);
        }
        int mid = (left + right) / 2;
        return Merge(divideMerge(lists,left,mid),divideMerge(lists,mid + 1,right));
    }
    public ListNode mergeKLists (ArrayList<ListNode> lists) {
        // write code here
        //双指针加上分治
        return divideMerge(lists,0,lists.size() - 1);
    }

    //使用优先级队列。创建小根堆的方式
    //时间复杂度：O(NlogN) 空间复杂度：O(N)
    public  ListNode mergeKLists2 (ArrayList<ListNode> lists) {
        //输入：[{1,2,3},{4,5,6,7}],我们的lists的长度w为2；0位置是{1,2,3} 1位置是{4,5,6,7}
        // write code here
        //默认为小根堆
        //这里要添加一个比较器，要不然会报错，可以使用 Lambda 表达式来简单的添加
        Queue<ListNode> queue = new PriorityQueue<>((v1,v2) -> (v1.val - v2.val));
        //把所有链表的第一个节点都放到堆中进行排序
        for(int i = 0;i < lists.size();i++) {
            //不为空就入堆,这里相当于入的是 1 和 4
            if(lists.get(i) != null) {
                queue.add(lists.get(i));
            }
        }

        ListNode ret = new ListNode(-1);
        ListNode head = ret;
        //不为空，我们就进行出堆和入堆的操作
        while(!queue.isEmpty()) {
            //每次出堆的堆顶数据都是最小的
            ListNode cur = queue.poll();

            head.next = cur;
            head = head.next;

            //出完堆之后，我们要进行入堆操作，把出堆的数据的下一个数据进行入堆，这里比如：出的是1，那么这里入堆的是2
            if(cur.next != null) {
                queue.add(cur.next);
            }
        }

        //到这里就合并结束
        return ret.next;
    }


    //BM2 链表内指定区间反转
    //时间复杂度：O(N) 空间复杂度：O(1)
    public class ListNode {
        int val;
        ListNode next = null;
        public ListNode(int val) {
            this.val = val;
        }
    }
    public ListNode reverseBetween (ListNode head, int m, int n) {
        // write code here
        //定义一个带哨兵位的ret链表，用来存储反转后的整体链表
        ListNode ret = new ListNode(-1);
        ret.next = head;
        //定义pre和cur
        ListNode pre = ret;
        ListNode cur = head;
        //先把cur走到我们要反转的位置
        //pre是cur的前面一个节点
        for(int i = 1;i < m;i++) {
            pre = cur;
            cur = cur.next;
        }
        //这个时候我们来进行翻转我们要翻转节点的范围
        for(int i = m;i < n;i++) {
            ListNode curNext = cur.next;
            cur.next = curNext.next;

            curNext.next = pre.next;
            pre.next = curNext;
        }
        return ret.next;
    }

    //最大连续 1 的个数 三
    //https://leetcode.cn/problems/max-consecutive-ones-iii/
    public int longestOnes(int[] nums, int k) {
        //滑动窗口，这个具有单调性
        int ret = 0;
        for(int left = 0,right = 0,zero = 0;right < nums.length;right++) {
            if(nums[right] == 0) {
                //当right 指向的为0的时候，入窗口
                zero++;
            }
            while (zero > k) {
                //当zero的数量超过的时候，我们就进行出窗口，但是需要等left执行也为0的时候
                if(nums[left++] == 0) {
                    zero--;
                }
            }
            //更新数据
            ret = Math.max(ret,right - left + 1);
        }
        return ret;
    }

    //长度最小的子数组
    //https://leetcode.cn/problems/minimum-size-subarray-sum/
    public int minSubArrayLen(int target, int[] nums) {
        int n = nums.length,sum = 0,len = Integer.MAX_VALUE;
        //这里的len求最小值，如果我们用0的话，返回的始终都是0，使用大的值，不知道最大是多少，所以直接使用int的极限
        for(int left = 0,right = 0;right < n; right++) {
            sum += nums[right];
            while(sum >= target) {
                //更新数据，并且出窗口
                len = Math.min(len,right - left + 1);
                sum -= nums[left++];
            }
        }
        return len == Integer.MAX_VALUE ? 0 : len;
    }
}
